package org.example.SolutionNew005;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Backtrack006 {
    public static void main(String[] args) {
        Backtrack006 b = new Backtrack006();
        String s=new String("aab");
        System.out.println(b.partition(s).toString());

    }

    boolean[][] dp;
    List<List<String>> res;
    public List<List<String>> partition1(String s) {
        //回文子串一般避不开二维数组
        int n = s.length();
        dp = new boolean[n][n];
        res = new ArrayList<>();

        for(int i=0;i<n;i++){
            Arrays.fill(dp[i],true);
        }

        for(int i=n-1;i>=0;i--){
            for(int j=i+1;j<n;j++){
                dp[i][j]=s.charAt(i)==s.charAt(j)&&dp[i+1][j-1];
            }
        }
        List<String> list = new ArrayList<>();
        dfs(s,n,0,list);
        return res;
    }

    public void dfs(String s,int n,int i,List<String> list){
        if(i==n){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int j=i;j<n;j++){
            if(dp[i][j]){
                list.add(s.substring(i,j+1));
                dfs(s,n,j+1,list);
                list.remove(list.size()-1);
            }
        }
    }

    //回溯+记忆化，边遍历s边记录是否回文
    int[][] f;
    List<List<String>> result;
    List<String> temp=new ArrayList<>();
    public List<List<String>> partition(String s) {
        int n = s.length();
        f = new int[n][n];
        result = new ArrayList<>();
        dfs_2(s,n,0);
        return result;
    }

    public void dfs_2(String s,int n,int i){
        if(i==n){
            result.add(new ArrayList<>(temp));
            return;
        }
        for(int j=i;j<n;j++){
            if(isPalin(s,i,j)==1){
                temp.add(s.substring(i,j+1));
                dfs_2(s,n,j+1);
                temp.remove(temp.size()-1);
            }
        }
    }

    public int isPalin(String s,int i,int j){
        if(f[i][j]!=0){
            return f[i][j];
        }
        //若为0说明还没有被检测过
        if(i>=j){
            f[i][j]=1;
        }else if(s.charAt(i)==s.charAt(j)){
            f[i][j]=isPalin(s,i+1,j-1);
        }else{
            f[i][j]=-1;
        }
        return f[i][j];
    }

}
